procedure siftup(i : longint);

var 
	k : longint;
	t : pair;
  
begin
	k := i shr 1;
	while (i > 1) and (a[k].a > a[i].a) do begin
		t := a[i];
		a[i] := a[k];
		a[k] := t;
		i := k;
		k := i shr 1;
	end;
end;

procedure insert(v : pair);
begin
	inc(n);
	a[n] := v;
	siftup(n);
end;

procedure siftdown(i : longint);

var 
	j, k : longint;
	t : pair;
	
begin
	k := i shl 1;
	while k <= n do begin
		j := i;
		if a[k].a < a[j].a then j := k;
		if (k + 1 <= n) and (a[k + 1].a < a[j].a) then j := k + 1;
		if i < j then begin
			t := a[i];
			a[i] := a[j];
			a[j] := t;
			i := j;
		end else break;
		k := i shl 1;
	end;
end;

function exMin() : pair;
begin
	result := a[1];
	a[1] := a[n];
	dec(n);
	siftdown(1);
end;

function mp(a, b : longint) : pair;
begin
	result.a := a;
	result.b := b;
end;

function dijkstra() : longint;  // m - Vertex Count

var
	v, cd, tto, len, i, tt : longint;
  d : array[0..110] of longint;
	p : pair;

begin
	for i := 1 to m do
		d[i] := INF;
	d[s] := 0;
	n := 0;
	insert(mp(0, s));
	while n > 0 do begin
		p := exMin();
		v := p.b;
		cd := p.a;
		if cd <= d[v] then begin
			tt := length(g[v]) - 1;
			for i := 0 to tt do begin
				tto := g[v][i].a;
				len := g[v][i].b;
				if d[v] + len < d[tto] then begin
					d[tto] := d[v] + len;
          //pr[tto] := v;
					insert(mp(d[tto], tto));
				end;
			end;
		end;
	end;
	if d[t] = INF then result := -1 else result := d[t];
end;